1. Field of the Invention
The present invention relates to switching of data packets in a non-blocking network switch configured for switching data packets between subnetworks.
2. Background Art
Local area networks use a network cable or other media to link stations on the network. Each local area network architecture uses a media access control (MAC) enabling network interface devices at each network node to access the network medium.
The Ethernet protocol IEEE 802.3 has evolved to specify a half-duplex media access mechanism and a full-duplex media access mechanism for transmission of layer 2 type data packets. A layer 2 type data frame (also referred to as a layer 2 type data packet) is defined as a data frame having a layer 2 header (e.g., Ethernet), a corresponding payload, and a cyclic redundancy check field (also referred to as a frame check sequence field) having a value based on the layer 2 header and the corresponding payload. The full-duplex media access mechanism provides a two-way, point-to-point communication link between two network elements, for example between a network node and a switched hub for simultaneous transmission and reception.
Switched local area networks are encountering increasing demands for higher speed connectivity, more flexible switching performance, and the ability to accommodate more complex network architectures. For example, commonly-assigned U.S. Pat. No. 5,953,335 discloses a network switch configured for switching layer 2 type Ethernet (IEEE 802.3) data packets between different network nodes; a received layer 2 type data packet may include a VLAN (virtual LAN) tagged frame according to IEEE 802.1p (802.1D) protocol that enables the network switch to perform more advanced switching operations. For example, the VLAN tag may specify another subnetwork (via a router) or a prescribed group of stations.
A particular concern in high-performance switches is the allocation of switch resources, such as output bandwidth, to different priority queues. Weighted fair queuing is a scheduling algorithm used to prioritize resources, where a certain output queue will be given a higher output bandwidth based on determined priorities. Weighted fair queuing, however, cannot be economically implemented in hardware because of complex processing requirements involving calculation of real numbers and a virtual clock implementation.
Weighted round robin is an integer-based scheduling algorithm that is substantially less complex and hence easier to implement in hardware. However, implementation of the weighted round robin in a network switch introduces additional problems, depending on the resource that the integer represents. For example, if weighted round robin scheduling is used to service the data flows on a byte basis, latencies may be introduced that disrupt the desired fair sharing behavior. If weighted round robin scheduling is used to service the data flows on a packet basis, there may be a chance that a flow having a large sized packet may unfairly use up all available bandwidth, depriving other flows from obtaining the requested bandwidth.